package com.sean.sort;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 *  选择排序： 直接选择排序，归并排序，堆排序
 */
public class SelectSort {
    /**
     * 直接选择排序原理：
     *      逐个找出第 i 小的记录，将其放到数组的第 i 个位置
     * @param array 待排序数组
     */
    public static void directSelectSort(int[] array){
        long start = System.nanoTime();
        if(array.length <= 1){
            return;
        }
        for(int i = 0; i < array.length; i++){
            int min = array[i];
            int minIndex = i;
            for(int j = i + 1; j < array.length; j++){
                if(array[j] < min){
                    min = array[j];
                    minIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
        long end = System.nanoTime();
        System.out.println("直接选择排序用时： " + (end - start) + "ns");
    }

    /**
     * 归并排序
     * @param array 待排序数组
     */
    public static void mergeSort(int[] array){
        long start = System.nanoTime();
        if(array.length <= 1){
            return;
        }
        int[] temp = Arrays.copyOf(array, array.length);     // 公共空间用于优化合并的性能
        sort(array, temp, 0, array.length - 1);   // 归并排序 (左闭右闭)
        long end = System.nanoTime();
        System.out.println("归并排序用时： " + (end - start) + "ns");
    }

    /**
     * 归并排序 —— 拆分 + 合并
     * @param array 待排序数组
     * @param temp 辅助数组
     * @param left 开始排序的左边界（闭区间）
     * @param right 开始排序的右边界（闭区间）
     */
    private static void sort(int[] array, int[] temp, int left, int right){
        if(left < right){
            int mid = left + (right - left) / 2;
            sort(array, temp, left, mid);
            sort(array, temp, mid + 1, right);
            merge(array, temp, left, right, mid);
        }
    }

    /**
     * 归并排序 —— 合并
     * @param array 待排序数组
     * @param temp 辅助数组
     * @param left 开始合并的左边界（闭区间）
     * @param right 开始合并的右边界（闭区间）
     * @param mid 两个区间的中间边界（属于左区间的右边界，闭区间）
     */
    private static void merge(int[] array, int[] temp, int left, int right, int mid){
        // 没有额外的空间开销
        // 将 array 数组从 left 开始拷贝 right - left + 1 个元素（左闭右开）到 temp 数组的 left 处
        System.arraycopy(array, left, temp, left, right - left + 1);
        int index1 = left;
        int index2 = mid + 1;
        int i = left;
        while(index1 <= mid && index2 <= right){
            if(temp[index1] < temp[index2]){
                array[i] = temp[index1];
                index1 ++ ;
                i ++;
            }else{
                array[i] = temp[index2];
                index2 ++;
                i ++;
            }
        }
        while(index1 <= mid){
            array[i] = temp[index1];
            index1 ++;
            i ++;
        }
        while(index2 <= right){
            array[i] = temp[index2];
            index2 ++;
            i ++;
        }
    }

    /**
     * 堆排序
     * @param array： 待排序数组
     */
    public static void heapSort(int[] array){
        long start = System.nanoTime();
        Queue<Integer> priorityQueue = new PriorityQueue<>(array.length, (a, b)-> a - b);   // 小顶堆
        for (int value : array) {
            priorityQueue.offer(value);
        }
        for(int i = 0; i < array.length; i++){
            array[i] = priorityQueue.poll();
        }
        long end = System.nanoTime();
        System.out.println("堆排序用时： " + (end - start) + "ns");
    }

    public static void main(String[] args) {
        final int _10w = 100000;
        // 直接选择排序用时： 5427373700ns
        int [] test1 = new int[_10w];
        for(int i = _10w, j = 0; i > 0; i--, j++){
            test1[j] = i;
        }
        SelectSort.directSelectSort(test1);

        // 归并排序用时： 8440000ns
        int [] test2 = new int[_10w];
        for(int i = _10w, j = 0; i > 0; i--, j++){
            test2[j] = i;
        }
        SelectSort.mergeSort(test2);

        // 堆排序用时： 63238200ns
        int [] test3 = new int[_10w];
        for(int i = _10w, j = 0; i > 0; i--, j++){
            test3[j] = i;
        }
        SelectSort.heapSort(test3);
    }
}
